redis底层数据结构解析

image-20210707145917303

sds(简单动态字符串)

redis并没有使用c语言中的字符串而是使用的自定义的sds,以解决一些c语言字符串会出现的问题以及进行性能优化

结构如下:

len:当前字符串长度

free:分配的空间所剩余的长度

buf:字符串的实体(不包含结束符)

问题1:c的字符串本身不记录字符串长度,如果要获取字符串长度,时间复杂度为O(n)

sds:数据结构中带有字符串的长度,和预留空间的长度

问题2:c中的字符串不记录自身长度容易造成缓冲区溢出

sds:当数据修改时,先判断内部的free是否满足容纳新字符串,如果不够就先进行扩容,扩容规则为:若数据长度小于1m就翻倍,大于1m就每次+1m

问题3:经常修改字符串会频繁修改字符串的空间分配,影响性能

sds:

  • 空间预分配
    • 就是指sds进行空间扩容时的规则,并不会只扩容所需的内存,通常情况会剩余一些额外的内存以便下次扩容使用
  • 惰性空间释放
    • 若修改sds减少时,并不会像想象中的减少对其所分配的内存,而是先将不用的内存放入free中,以便下次扩容,当然也有对应的主动释放空间的api

问题4:特殊字符保存

sds:sds是对二进制安全的,不会对数据做任何限制,也可以保存特殊字符,因为读取数据的判断是根据len,而不是结束符

双向链表(listnode)

  • 双端:链表节点带有pre 和 next 指针,获取某个节点的前置节点和后置节点的复杂度为O(n)
  • 无环:表头的节点 head 的prev指针和 表尾节点 next 都指向了Null,说明链表的访问结束了
  • 获取链表长度:list 的len 属性,可以直接获取链表的长度,复杂度O(1)
  • 多态:链表节点使用void* 指针来保存节点值,可以保存各种不同类型的值。
  • 获取表头和表尾数据负责度O(1)

压缩列表(ziplist)

是一种特殊的双向链表

压缩链表与经典双端链表最大的区别在于,双端链表的节点是分散在内存中并不是连续的,压缩链表中所有的数据都是存储在一段连续的内存之中的,时间换空间。

具体内部参数:https://juejin.cn/post/6974706255138914341#heading-6

哈希表

本质是一个列表,列表内部的元素是一个链表,链表的每一个结点存着键值对

这种方式叫做链地址法,用于解决hash冲突,在数组桶位相同的情况下将插入的结点插入到链表表头,所以hash在插入寻址的时间复杂度是o1

typedef struct dictht{
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码,用于计算索引值
    // 总是等于 size-1
    unsigned long sizemask;

    // 该哈希表已有节点数量
    unsigned long used;
} dictht

结点

typedef struct dictEntry {
    // 键
    void *key;

    // 值
    union {
        void *val;
        unit64_t u64;
        nit64_t s64;
    } v;

    // 指向下一个哈希表节点,形成链表
    struct dictEntry *next;
} dictEntry;

整数集合

是redis中set的底层实现之一,使用场景比较少

它的特点有:

元素类型只能为数字。
元素有三种类型:int16_t、int32_t、int64_t。
元素有序,不可重复。
内存连续,来节省内存空间。

跳表

个人总结

跳表是一种特殊的数据结构,存在多层次链表,每上一层链表都是下一层链表的子集,每一层可以看做是索引层

https://juejin.cn/post/6974706255138914341#heading-4